package digui;

public class _010寻找发帖水王 {
    /*
    Tango是微软亚洲研究院的一个试验项目。研究院的员工和实习生们都很喜欢在Tango上面交流灌水。
    传说，Tango有一大“水王”，他不但喜欢发贴，还会回复其他ID发的每个帖子。坊间风闻该“水王”
    发帖数目超过了帖子总数的一半。如果你有一个当前论坛上所有帖子（包括回帖）的列表，其中帖子作
    者的ID也在表中，你能快速找出这个传说中的Tango水王吗？
     */
    public static void main(String[] args) {
        int[] a = {1,2,1,1};
        solve(a);
        solve2(new int[]{1,2,3,4,4,4,});
    }

    //使用两两消除法，确定第一个元素为候选值，一个变量记下此候选值出现的次数
    //循环数组，如果下一个元素和当前候选值不同，候选值和次数都消为0
    //继续循环，下一个值为候选值，若下一个值和候选值相同， 次数加1
    public static void solve(int[] a){
        int candidate = a[0];   //先选定第一个值为候选值
        int nTime = 1;   //出现的次数
        for (int i = 1; i<a.length; i++){
            //两两消减为0，将当前元素作为候选值
            if (nTime == 0){
                candidate = a[i];
                nTime = 1;
                continue;
            }
            //遇到相同的，次数加一
            if (a[i] == candidate){
                nTime++;
            }else {
                //不同的，次数减一
                nTime--;
            }
        }
        System.out.println(candidate);
    }

    // //变化，出现次数恰好为个数的一半，求出这个数
    //  /*
    //  * 关于加强版水王的题我有个想法可以扫描一遍数组就解决问题：
    //    水王占总数的一半，说明总数必为偶数；
    //    不失一般性，假设隔一个数就是水王的id，两两不同最后一定会消减为0
    //    水王可能是最后一个元素，每次扫描的时候，多一个动作，和最后一个元素做比较，单独计数，计数恰好等于一半
    //    如果不是，计数不足一半，那么去掉最后一个元素，水王就是留下的那个candidate*/
    public static void solve2(int[] a){
        int candidate = a[0];
        int nTime = 1;
        int countOfLast = 0;
        int N = a.length;
        for (int i = 1;i < a.length;i++){
            if (a[i] == a[a.length-1]){
                countOfLast +=1;
            }
            if (nTime == 0){
                candidate = a[i];
                nTime =1;
                continue;
            }
            if (a[i] == candidate){
                nTime++;
            }else {
                nTime--;
            }
        }
        //最后一个元素出现次数是n/2
        if (countOfLast == N / 2){
            System.out.println(a[N - 1]);
        } else{
            System.out.println(candidate);
        }
    }
}
